class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> arr; // 大小代表最长长度，值代表这个长度的子序列的最后一个值
        arr.push_back(nums[0]);
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] > arr.back())
            {
                arr.push_back(nums[i]);
            }
            else // 二分找到要放的位置（找大于等于nums[i]的左端点）
            {
                int left = 0, right = arr.size() - 1;
                while(left < right)
                {
                    int mid = (right + left) >> 1; // 元素个数是偶数时，中点是中间的左边
                    if(arr[mid] < nums[i])
                        left = mid + 1;
                    else // (arr[mid] >= nums[i])
                        right = mid; // 自己可能是左端点
                }
                arr[left] = nums[i];
            }
        }
        return arr.size();
    }
};